#ifndef MyList_H
#define MyList_H
template<typename Object>
class MyList{
private:
	struct Node{
		Object data;
		Node *prev;
		Node *next;
		Node(const Object &d = Object(), Node *p = NULL, Node *n = NULL): data(d),prev(p),next(n){}
	};
	int theSize;
	Node *head;
	Node *tail;
	void Init(){
		theSize = 0;
		head = new Node;
		tail = new Node;
		head->next = tail;
		tail->prev = head;
	}
public:
	class const_iterator{
	protected:
		Node *current;
		const_iterator(Node *p):current(p){}
		Object& retrieve()const{
			return current->data;
		}
		friend class MyList<Object>;
	public:
		const_iterator():current(NULL){}
		const Object& operator*() const{
			return current->data;
		}
		const_iterator& operator++(){
			current = current->next;
			return *this;
		}
		const_iterator operator++(int){
			const_iterator p(current);
			current = current->next;
			return p;
		}
		bool operator==(const const_iterator& rhs) const{
			return current==rhs.current;
		}
		bool operator!=(const const_iterator& rhs)const{
			return current!=rhs.current;
		}
	};
	class iterator : public const_iterator{
	protected:
		friend class MyList<Object>;
		iterator(Node* p):const_iterator(p){}
	public:
		iterator(){}
	    Object& operator*(){
			return current->data;
		}
		const Object& operator*()const{
			const_iterator::operator*();
		}
		iterator& operator++(){
			current = current->next;
			return current->data;
		}
		iterator& operator--(){
			current = current->prev;
			return *this;
		}
		iterator operator++(int){
			iterator p(current);
			current = current->next;
			return p;
		}
	};
public:
	MyList() {
		Init();
	}
	MyList(const MyList& rhs){
		Init();
		*this = rhs;
	}
	~MyList(){
		clear();
		delete head;
		delete tail;
	}
	const MyList& operator=(const MyList &rhs){
		if(this != &rhs){
			theSize = rhs.theSize;
			clear();
			for(const_iterator it = rhs.begin(); it != rhs.end(); it++)
				push_back(*it);
		}
		return *this;
	}
	iterator begin(){
		return iterator(head->next);
	}
	const_iterator begin() const{
		return const_iterator(head->next);
	}
	iterator end(){
		return iterator(tail);
	}
	const_iterator end()const{
		return const_iterator(tail);
	}
	int size() const{
		return theSize;
	}
	bool empty()const{
		return theSize==0;
	}
	void clear(){
		while(!empty()){
			pop_front();
		}
	}
	Object& front(){
		return begin()->data;
	}
	const Object& front() const{
		return begin()->data;
	}
	Object& back(){
		return (--end())->data;
	}
	const Object& back()const{
		return (--end())->data;
	}
	void push_front(Object& obj){
		insert(begin(),obj);
	}
	void push_back(Object& obj){
		insert(end(),obj);
	}
	void pop_front(){
		erase(begin());
	}
	void pop_back(){
		erase(--end());
	}

	iterator insert(iterator it, const Object &obj){
		Node *node = new Node(obj);
		node->next = it.current;
		node->prev = it.current->prev;
		it.current->prev->next = node;
		it.current->prev = node;
		theSize++;
		iterator retVal(node);
		return retVal;
	}
	iterator erase(iterator it){
		Node *p = it.current;
		p->prev->next = p->next;
		p->next->prev = p->prev;
		iterator retVal(p->next);
		delete p;
		theSize--;
		return retVal;
	}
	iterator erase(iterator start,iterator end){
		while(start != end){
			start = erase(start);
		}
		return end;
	}
};
#endif